#pragma once

#include <vector>

namespace jianzhi_036
{

class Node
{
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val)
    {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right)
    {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Solution
{
public:
    Node* treeToDoublyList(Node* root)
    {
        if (root == nullptr)
            return root;
        inorder(root);
        m_tail->right = m_head.right;
        m_head.right->left = m_tail;
        return m_head.right;
    }

private:
    void inorder(Node* head)
    {
        if (head == nullptr)
            return;
        inorder(head->left);
        m_tail->right = head;
        head->left = m_tail;
        m_tail = head;
        inorder(head->right);
    }

    Node m_head{0, nullptr, nullptr};
    Node* m_tail = &m_head;
};

}  /* namespace jianzhi_036 */
